Advent of Code 2020: Day 7

This day in Advent of Code is about bags containing other bags. These other bags contain other bags, and so on and so forth. The input explains which bags contain which other bags and the amount. Below is an example input (The real input is much much longer):

light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.

Part 1

The first part is to figure out how many bags can contain a shiny gold bag. In the example input above the following bags may contain a shiny gold bag:

bright white -> shiny gold
muted yellow -> shiny gold
dark orange -> bright white -> shiny gold
light red -> bright white / muted yellow -> shiny gold

i.e. a total of 4 (four) bags can contain a shiny gold bag. To solve the exercise, I start out by treating the data to a nice round of regular expressions. I then put them all in a dictionary called rules where the key (index) is the bag name and the value is another dictionary with each bag that may be contained and how many. The code for doing this is quite short but uses a both the regular expressions library and the defaultdict from the collections library (both built-in):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import re
from functools import lru_cache # We will use this later
from collections import defaultdict

re_bagtype = re.compile(r"^(\w+ \w+)")
re_contains = re.compile(r"(\d)+ (\w+ \w+)")

with open("input/day07.txt") as file:
    rule_specification = file.readlines()

rules = defaultdict(dict)
for line in rule_specification:
    rule = {}
    for amount, bag in re_contains.findall(line):
        rule[bag] = int(amount)
    rules[re_bagtype.findall(line)[0]] = rule

Onto the actual challenge… How do we determine if a bag A may contain a shiny one? If bag A description tells us that it includes one, then it is obvious. If bag A does not, we must check all bags which may exist inside bag A. This problem naturally calls for recursion. When using this, the solution actually becomes shockingly easy. I create a function which takes a bag and returns all bags which may be contained within all the way down. This function starts by creating a set of itself. A Python set is like a list, where repeated elements are ignored. For each rule in the rules we simply call the function and update the set of contained bags. We can do this update, since the function eventually returns the set of bags. Hence, when it reaches a bag that contains no other bags it will return, and the previous function can return, and the previous, and so on until the initial call is returned. I also add the amount of bags it may contain as I can foresee the future. The function is seen below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

@lru_cache(maxsize=1024)
def contained_within(bag):
    # This implementation results in a bag containing itself and the end of
    # recursion. This is accounted for in part1() and part2().
    bag_total = set([bag])
    amount_total = 1
    for b, m in rules[bag].items():
        b_r, m_r = contained_within(b)
        # We update bags and amounts from the recursive call.
        bag_total.update(b_r)
        amount_total += m * m_r
    return bag_total, amount_total

Without line 1 in the above code, I cannot complete the challenge before my patience runs out (about 10 minutes). Line 1 which features the Least Recently Used (LRU) type of caching method, which caches (remembers) the most recent outputs. For example, if my computer just expended a bunch of resources calling contained_within() of faded magenta bags and now needs the answer again a couple of operations later, the caches just provides it since it has it stored. The code in line 1 is a functools wrapper for functions which implements such an LRU cache without having to program it yourself.

To get the answer to part 1 I call contained_within() on every bag in rules and count the occurences of shiny gold:

1
2
3

def part1():
    return (sum(["shiny gold" in contained_within(b)[0]
                 for b in rules.keys()]) - 1)

Part 2

Now we must find how many bags are contained within the shiny gold bag. This is where the foresight of my function comes into play. We can simply call the function on shiny gold and look at amount_total:

1
2

def part2():
    return contained_within("shiny gold")[1] - 1

Day 7 of Advent was overall a quite fun recursive exercise.

The full code for this day can be found here. The entire repository is available at GitHub.